Soal dan Pembahasan – Induksi Matematika pada Keterbagian Bilangan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): n^3 -n$ habis dibagi $6.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 1^3 -1 = 0$ habis dibagi $6$.
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k): k^3 -k$ habis dibagi $6$ merupakan pernyataan yang diasumsikan benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan $P(k+1): (k+1)^3 -(k+1)$ habis dibagi $6$.
Ekspresi pada $P(k+1)$ dapat ditulis menjadi
$$\begin{aligned} (k+1)^3 -(k+1) & = k^3 + 3k^2 + 2k \\ & = (n^3 -n) + (3n^2 + 3n) \\ & = (n^3 -n) + 3n(n+1). \end{aligned}$$Ekspresi terakhir terdiri dari dua suku. Suku pertama adalah $(n^3 – n)$ yang habis dibagi $6$ berdasarkan asumsi sebelumnya. Suku kedua adalah $3n(n+1)$, juga habis dibagi $6$ karena mengandung faktor $3$ dan salah satu di antara $n$ atau $n+1$ merupakan bilangan genap sehingga mengandung faktor $2$. Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$
Catatan: Suatu bilangan habis dibagi $6$ jika dan hanya jika bilangan itu habis dibagi $2$ (genap) sekaligus habis dibagi $3$.

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): 3~|~n^3 + 2n.$
Langkah Basis:
Untuk $n = 1$, diperoleh $P(1): 3~|~1^3 + 2(1).$
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku $P(k): 3~|~k^3+2k.$
Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 3~|~(k+1)^3+2(k+1).~~\bigstar$
Perhatikan bahwa
$$\begin{aligned} (k+1)^3+ 2(k+1) & = (k^3+3k^2+3k+1)+(2k+2) \\ & = (k^3+2k) + 3(k^2+k+1). \end{aligned}$$Karena $k^3+2k$ merupakan kelipatan $3$ (berdasarkan asumsi) dan $3(n^2+n+1)$ jelas habis dibagi $3$ (karena mengandung faktor $3$), maka $(k^3+2k) + 3(k^2+k+1)$ juga merupakan kelipatan $3$.
Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): 7^n -2^n$ habis dibagi $5.$
Langkah Basis:
Untuk $n = 1$, diperoleh $P(1): 7^1 -2^1=5$, yang jelas habis dibagi $5.$
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k): 7^k -2^k$ habis dibagi $5$ diasumsikan merupakan pernyataan yang benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan $P(k+1): 7^{k+1} -2^{k+1}$ habis dibagi $5.$
Bentuk pada $P(k+1)$ di atas dapat ditulis menjadi
$\begin{aligned} & 7^k \cdot 7 -2^k \cdot 2 \\ & = 7^k \cdot 7 -7 \cdot 2^k + 7 \cdot 2^k -2^k \cdot 2 \\ & = 7(7^k -2^k) + 2^k(7-2) \\ & = 7(7^k -2^k) + 2^k(5). \end{aligned}$
Ekspresi terakhir di atas terdiri dari $2$ suku. Suku pertama adalah $7(7^k -2^k)$ habis dibagi $5$ karena faktor $7^k -2^k$ habis dibagi $5$ berdasarkan asumsi sebelumnya. Suku kedua adalah $2^k(5)$ jelas habis dibagi $5$ karena mengandung faktor $5$. Dengan demikian, secara keseluruhan, $7^{k+1} -2^{k+1}$ habis dibagi $5$.
Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): a^{2n-1} + b^{2n-1}$ habis dibagi oleh $a + b.$
Langkah Basis:
Untuk $n = 1,$ diperoleh $P(1): a + b$ habis dibagi oleh $a +b$ (dirinya sendiri),  jelas merupakan pernyataan yang benar. Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku $P(k): a^{2k-1} + b^{2k-1}$ habis dibagi oleh $a + b$. Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan $P(k+1): a^{2k+1} + b^{2k+1}$ habis dibagi oleh $a + b.$
Perhatikan bahwa
$$\begin{aligned} a^{2k+1} + b^{2k+1} & = a^{2k-1} \cdot a^2 + b^{2k-1} \cdot b^2 \\ & = (a^{2k-1} + b^{2k-1}) (a^2) -b^{2k-1}(a^2-b^2) \\ & = (a^{2k-1} + b^{2k-1}) (a^2) -b^{2k-1}(a+b) (a-b). \end{aligned}$$Ekspresi di atas terdiri dari dua suku. Suku pertama adalah $(a^{2k-1}+b^{2k-1})(a^2)$, habis dibagi oleh $a + b$ karena faktor pertamanya telah diasumsikan habis dibagi oleh $a + b,$ sedangkan suku keduanya, yaitu $-b^{2k-1}(a+b) (a-b)$ jelas habis dibagi $a + b$ karena mengandung faktor tersebut.
Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): n^3 + 5n$ habis dibagi $6.$
Langkah Basis:
Untuk$n = 1$, diperoleh
$P(1): 1^3 + 5(1) = 6$ habis dibagi $6$.
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): k^3 + 5k$ habis dibagi $6$.
Asumsikan pernyataan di atas benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): (k+1)^3 + 5(k+1)$ habis dibagi $6$.
Ekspresi $P(k+1)$ di atas dapat ditulis menjadi$$(k+1)^3 + 5(k+1) = (k^3+ 5k) + 3(k^2 + k + 2)$$jika diuraikan pangkatnya.
Sekarang dua suku pada ekspresi terakhir akan kita tinjau sebagai berikut. Suku pertama yaitu $k^3 + 5k$ habis dibagi $6$ berdasarkan asumsi sebelumnya. Suku kedua yaitu $3(k^2 + k + 2)$ juga habis dibagi $6$ karena ekspresi ini habis dibagi $3$ (mengandung faktor $3$) serta habis dibagi $2$ sebab ($k^2 + k +2$) merupakan bilangan genap untuk setiap $k \in \mathbb{N}$. Karena kedua sukunya habis dibagi $6$, ekspresi keseluruhan juga habis dibagi $6.$
Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): x^n -1$ habis dibagi oleh $x -1.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): x -1$ habis dibagi oleh $x -1.$
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): x^k -1$ habis dibagi oleh $x -1.$
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): x^{k+1} -1$ habis dibagi oleh $x -1.$ 
Perhatikan bahwa
$\begin{aligned} x^{k+1} -1 & = x \cdot x^k -1 \\ & = x \cdot x^k -1 + (x -x) \\ & = \underbrace{x(x^k -1)}_{\text{habis dibagi}~(x+1)} + \color{blue}{(x -1)}. \end{aligned}$
Perhatikan ekspresi terakhir. Suku pertama (yang telah diberi keterangan) habis dibagi $x -1$ berdasarkan asumsi bahwa $P(k)$ benar, yaitu $x^k -1$ habis dibagi $x -1$, sedangkan suku kedua (yang diberi warna biru) jelas habis dibagi oleh $x- 1$ (dirinya sendiri). Untuk itu, keduanya habis dibagi oleh $x-1$ sehingga pernyataan $P(k+1)$ terbukti benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n)$ : Salah satu faktor dari $n^3+3n^2+2n$ adalah $3.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1)$: Salah satu faktor dari $1^3+3(1)^2+2(1) = 6$ adalah $3$. 
Pernyataan di atas benar (faktor dari $6$ adalah $1, 2, 3$, dan $6$). Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: Salah satu faktor dari $k^3+3k^2+2k$ adalah $3$. 
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1)$: Salah satu faktor dari $(k+1)^3+3(k+1)^2+2(k+1)$ adalah $3.$
Sekarang kita akan mengubah (memanipulasi) bentuk $(k+1)^3+3(k+1)^2+2(k+1)$ sebagai berikut. 
$$\begin{aligned} (k+1)^3+3(k+1)^2 + 2(k+1) & = (k^3+3k^2+3k+1) + (3k^2 + 6k + 3) + (2k+2) \\ & = (k^3 + 3k^2 + 2k + k) + (3k^2 + 8k + 6) \\ & = (k^3 + 3k^2 + 2k) + (3k^2 + 9k + 6) \\ & = \underbrace{(k^3 + 3k^2 + 2k)}_{\text{memiliki faktor 3}} + \color{blue}{3(k^2 + 3k + 2)} \end{aligned}$$Dua suku pada ekspresi terakhir di atas memiliki $3$ sebagai salah satu faktornya. Untuk suku pertama (yang telah diberi keterangan), salah satu faktornya adalah $3$ berdasarkan asumsi bahwa $P(k)$ benar. Untuk suku kedua (yang diberi warna biru), salah satu faktornya juga $3$, jelas karena ditulis dalam bentuk pemfaktoran. 
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n)$: Salah satu faktor dari $2^{2n-1} + 3^{2n-1}$ adalah $5.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1)$: Salah satu faktor dari $2^{2(1)-1} + 3^{2(1)-1} = 2^1 + 3^1 = 5$ adalah $5$. 
Pernyataan di atas benar (faktor dari $5$ adalah $1$ dan $5$). Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: Salah satu faktor dari $2^{2k-1} + 3^{2k-1}$ adalah $5$. 
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1)$: Salah satu faktor dari $2^{2(k+1)-1} + 3^{2(k+1)-1} = 2^{2k+1} + 3^{2k+1}$ adalah $5$. 
Sekarang kita akan mengubah (memanipulasi) bentuk $2^{2k+1}+3^{2k+1}$ sebagai berikut. 
$$\begin{aligned} 2^{2k+1} + 3^{2k+1} & = 2^{2k-1+2} + 3^{2k-1+2} \\ & = 2^{2k-1} \cdot 2^2 + 3^{2k-1} \cdot 3^2 \\ & = 2^{2k-1} \cdot 4 + 3^{2k-1} \cdot 9 \\ & = 2^{2k-1}(5-1) + 3^{2k-1} \cdot (10-1) \\ & = 5 \cdot 2^{2k-1} -2^{2k-1} + 10 \cdot 3^{2k-1} – 3^{2k-1} \\ & = \color{blue}{5(2^{2k-1} + 3^{2k-1})}\underbrace{-(2^{2k-1} + 3^{2k-1})} _{\text{memiliki faktor 5}} \end{aligned}$$Dua suku pada ekspresi terakhir di atas memiliki $5$ sebagai salah satu faktornya. Untuk suku pertama (yang diberi warna biru), salah satu faktornya adalah $5$, jelas karena ditulis dalam bentuk pemfaktoran. Untuk suku kedua (yang telah diberi keterangan), salah satu faktornya juga $5$ berdasarkan asumsi bahwa $P(k)$ benar.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$  

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 41^n -14^n$ adalah kelipatan $27.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1): 41^1 -14^1 = 27$ adalah kelipatan $27.$ 
Pernyataan di atas jelas benar. Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: $41^k -14^k$ adalah kelipatan $27.$
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 41^{k+1} -14^{k+1}$ adalah kelipatan $27.$ 
Sekarang kita akan mengubah (memanipulasi) bentuk $41^{k+1} -14^{k+1}$ sebagai berikut. 
$\begin{aligned} & 41^{k+1} -14^{k+1} \\ & = 41^k \cdot 41 -14^k \cdot 14 \\ & = 41^k(27+14) -14^k \cdot 14 \\ & = 27 \cdot 41^k + 14 \cdot 41^k -14 \cdot 14^k \\ & = \color{blue}{27 \cdot 41^k} + \underbrace{14(41^k -14^k)}_{\text{berkelipatan 27}} \end{aligned}$
Dua suku pada ekspresi terakhir di atas memiliki berkelipatan $27$. Untuk suku pertama (yang diberi warna biru), memiliki kelipatan $27$, jelas karena ditulis dalam bentuk pemfaktoran. Suku kedua (yang telah diberi keterangan) juga berkelipatan $27$ berdasarkan asumsi bahwa $P(k)$ benar.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 2^{6n} + 3^{2n-2}$ habis dibagi $5.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 2^{6} + 3^{0} = 65$ habis dibagi $5.$
Pernyataan di atas jelas benar. Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: $2^{6k} + 3^{2k-2}$ habis dibagi $5.$ 
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1)$: $2^{6k+6} + 3^{2k}$ habis dibagi $5.$
Sekarang kita akan mengubah (memanipulasi) bentuk $2^{6k+6} + 3^{2k}$ sebagai berikut. 
$$\begin{aligned} 2^{6k+6} + 3^{2k} & = 2^{6k} \cdot 2^6 + 3^{2k-2} \cdot 3^2 \\ & = 2^{6k} \cdot (55 + 9) + 3^{2k-2} \cdot 9 \\ & = 2^{6k} \cdot 55 + 2^{6k} \cdot 9 + 3^{2k-2} \cdot 9 \\ & = 2^{6k} \cdot \color{blue}{5} \cdot 11 + \underbrace{(2^{6k} + 3^{2k-2})}_{\text{habis dibagi 5}} \cdot 9 \end{aligned}$$Perhatikan bahwa suku pertama pada ekspresi terakhir habis dibagi $5$ karena memuat faktor $5,$ sedangkan suku kedua habis dibagi $5$ karena asumsi kita pada langkah induktif bahwa $P(k)$ benar. Dengan demikian, penjumlahan dua suku tersebut juga habis dibagi $5.$
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 4.007^n -1$ habis dibagi $2.003.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1)$: $4.007^1-1 = 4.006$ habis dibagi $2.003.$ 
Jadi, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): 4.007^k -1$ habis dibagi $2.003.$
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 4.007^{k+1} -1$ habis dibagi $2003.$
Sekarang kita akan mengubah (memanipulasi) bentuk $4.007^{k+1}-1$ sebagai berikut. 
$$\begin{aligned} 4.007^{k+1}-1 & = 4.007^k \cdot 4.007 -1 \\ & = 4.007^k \cdot (2.003+2.004) -(2.004-2.003) \\ & = 2.003 \cdot 4.007^k + 2.004 \cdot 4.700^k – 2.004 + 2.003 \\ & = \underbrace{2.004(4.700^k -1)}_{\text{berkelipatan 2.003}} + \color{blue} {2.003(4.007^k + 1)} \end{aligned}$$Dua suku pada ekspresi terakhir di atas berkelipatan $2.003.$ Untuk suku pertama (yang telah diberi keterangan), memiliki kelipatan $2.003$ berdasarkan asumsi bahwa $P(k)$ benar. Untuk suku kedua (yang diberi warna biru), salah satu faktornya adalah $2.003$ sehingga jelas merupakan kelipatan $2003$. 
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): 2^{4n-1}$ habis dibagi $8.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 2^{4(1)-1} = 8$ habis dibagi $8$. Pernyataan ini benar. Untuk itu, $P(n)$ bernilai benar untuk $n = 1$. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): 2^{4k-1}$ habis dibagi $8$.
Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 2^{4(k+1)-1} = 2^{4k+3}$ habis dibagi $8$.
Perhatikan bahwa 
$\begin{aligned} 2^{4k + 3} & = 2^{4k -1 + 4} \\ & = 2^{4k -1} \times 2^{4} \\ & = 2^{4k -1} \times 16. \end{aligned}$
Karena $2^{4k-1}$ maupun $16$ habis dibagi $8$, $2^{4k+3}$ juga demikian.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

Misalkan $x$ merupakan bilangan asli. Definisikan $P(x): 5^{2x}+3x-1$ habis dibagi $9.$
Langkah Basis:
Untuk $x = 1$, diperoleh
$P(1): 5^2+3(1)-1 = 27$ habis dibagi $9.$ Pernyataan ini benar. Untuk itu, $P(x)$ bernilai benar untuk $x = 1$. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): 5^{2k}+3k-1$ habis dibagi $9$.
Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 5^{2(k+1)}+3(k+1)-1$ habis dibagi $9$.
Perhatikan bahwa 
$$\begin{aligned} 5^{2(k+1)}+3(k+1)-1 & = 5^{2k + 2} + 3k + 3-1 \\ & = \color{red}{25 \cdot 5^{2k}} + \color{blue}{3k} + \color{green}{2} \\ & = \color{red}{(18 \cdot 5^{2k} + 7 \cdot 5^{2k})} + \color{blue}{(21k-18k)} + \color{green}{(-7+9)} \\ & = (7 \cdot 5^{2k} + 21k-7) + (18 \cdot 5^{2k}-18k + 9) \\ & = 7\underbrace{(5^{2k} + 3k-1)}_{\text{habis dibagi}~9} + \underbrace{9(2 \cdot 5^{2k}-2k + 1)}_{\text{habis dibagi}~9}. \end{aligned}$$Karena suku pertama habis dibagi $9$ berdasarkan asumsi $P(k)$ benar dan suku kedua habis dibagi $9$ karena memuat faktor $9$, maka $7(5^{2k} + 3k-1) + 9(2 \cdot 5^{2k}-2k + 1)$ habis dibagi $9$ sehingga $P(k+1)$ terbukti benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(x)$ benar untuk setiap $x \in \mathbb{N}.$ $\blacksquare$  

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 2.002^{n+2} + 2.003^{2n+1}$ habis dibagi $4.005.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 2.002^3 + 2.003^3 = 16.060.078.035$ habis dibagi $4.005.$
Pernyataan di atas benar. Terkadang dalam membuktikan suatu pernyataan/rumus baru, kita perlu melakukan langkah basis untuk “beberapa” nilai $n$ pertama karena mungkin saja untuk $n$ tertentu, pernyataan yang diduga benar ternyata salah. Sekarang coba ambil $n = 2.$ 
$P_2: 2.002^3 + 2.003^5$ habis dibagi $4.005.$
Pernyataan di atas salah. Cara memeriksanya dengan cepat alias tanpa menghitung adalah mengamati nilai satuannya: $2^3 + 3^5 \Rightarrow 8 + 3 \rightarrow 1$, sedangkan $4.005$ memiliki satuan $5$, artinya bilangan yang dibagi harus memiliki satuan $5$). Jadi, langkah basis berakhir. Langkah induktif tidak dapat dilakukan dan kita simpulkan bahwa konjektur di atas bernilai salah. 
Catatan: Tidak semua proposisi terbukti benar dengan melakukan induksi. Bedakan istilah proposisi dan konjektur sebagai berikut. Suatu pernyataan yang kebenarannya masih diragukan disebut konjektur. Jika pernyataan itu terbukti benar ATAU salah, maka pernyataan itu disebut proposisi. 
Soal ini meminta kita untuk “memeriksa” (menyelidiki) sehingga langkah basis dapat dilakukan sampai beberapa nilai $n$ pertama (tujuannya untuk memastikan saja). Lagipula, jika soal ini diteruskan sampai langkah induktif, kita tidak dapat menemukan kesimpulan yang semestinya. Lebih lanjut, apabila soal berbunyi “buktikan/tunjukkan…. “, tetapi langkah basis berakhir setelah ditemukan pernyataan yang salah untuk $n$ tertentu, maka soal itu diasumsikan tidak valid.

Ide utamanya adalah ketika kita memiliki satu anggota tambahan, katakanlah $x$, pada sembarang himpunan dengan $n$ anggota, banyaknya himpunan bagian menjadi dua kali dari semula, yaitu himpunan bagian dari himpunan semula (tanpa memuat $x$) ditambah dengan himpunan bagian dari himpunan semula yang memuat $x.$
Dengan berlandaskan pada ide ini, kita akan membuktikan secara formal dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat $n \ge 0.$ Misalkan juga $P(n)$ menyatakan banyaknya himpunan bagian dari himpunan dengan $n$ anggota adalah $2^n.$
Langkah Basis:
$P(0)$ benar karena himpunan kosong memiliki $2^0 = 1$ himpunan bagian, yaitu dirinya sendiri. Langkah basis selesai.
Langkah Induktif:
Misalkan $P(k)$ menyatakan banyaknya himpunan bagian dari himpunan dengan $k$ anggota adalah $2^k$ untuk sembarang bilangan bulat $k \ge 0.$ Akan ditunjukkan bahwa $P(k+1)$ benar, artinya banyaknya himpunan bagian dari himpunan dengan $(k+1)$ anggota adalah $2^{k+1}.$
Misalkan terdapat sembarang himpunan $A$ dengan $(k+1)$ anggota dan terdapat $a_1 \in A.$ Notasi $\mathcal{S}(A)$ menyatakan himpunan kuasa (power set) dari $A.$
Karena himpunan bagian dari $A$ yang tidak memuat $a_1$ ada sebanyak $2^k$ (hipotesis induksi) dan himpunan bagian dari $A$ yang memuat $a_1$ juga sebanyak $2^k$, yaitu dengan menggabungkan $\{a_1\}$ pada masing-masing himpunan bagian semula, kita peroleh
$$|\mathcal{S}(A)| = 2^k + 2^k = 2^{k+1}.$$Jadi, $P(k+1)$ terbukti benar. Karena $P(0)$ benar dan untuk sembarang bilangan bulat $k \ge 0,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat $n \ge 0.$ $\blacksquare$

Untuk suatu bilangan asli $n > 1,$ misalkan $P(n)$ menyatakan bilangan $2^n$ dapat dituliskan sebagai penjumlahan dua bilangan ganjil berurutan.
Langkah Basis:
Untuk $n = 2,$ $P(2)$ benar karena $2^2 = 1 + 3$ sehingga $2^2$ dapat ditulis sebagai penjumlahan dua bilangan ganjil berurutan.
Langkah Induktif:
Ambil sembarang bilangan asli $k > 1.$ Asumsikan $P(k)$ benar, yaitu bilangan $2^k$ dapat dituliskan sebagai penjumlahan dua bilangan ganjil berurutan. Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu bilangan $2^{k+1}$ dapat dituliskan sebagai penjumlahan dua bilangan ganjil berurutan.
Karena $P(k)$ benar, kita dapat tuliskan $2^k = m + (m+2) = 2m + 2$ untuk suatu bilangan ganjil $m.$ Perhatikan bahwa
$$\begin{aligned} 2^{k+1} & = 2^k \cdot 2 \\ & = (2m + 2) \cdot 2 && (\text{Hipotesis induksi}) \\ & = (2m + 2) + (2m + 2)  \\ & = (2m + 1) + (2m + 3). \end{aligned}$$Karena $2m$ genap, maka $(2m+1)$ dan $(2m+3)$ merupakan bilangan ganjil, dan berurutan.
Jadi, $P(k+1)$ terbukti benar. Karena $P(2)$ benar dan untuk sembarang bilangan asli $k > 1,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n > 1.$ $\blacksquare$ 

Untuk suatu bilangan asli $n,$ misalkan $P(n)$ menyatakan bilangan $3^n$ dapat dituliskan sebagai penjumlahan tiga bilangan bulat berurutan.
Langkah Basis:
Untuk $n = 1,$ $P(1)$ benar karena $3^1 = 3 = 0 + 1 + 2$ sehingga $3^1$ dapat ditulis sebagai penjumlahan tiga bilangan bulat berurutan.
Langkah Induktif:
Ambil sembarang bilangan asli $k.$ Asumsikan $P(k)$ benar, yaitu bilangan $3^k$ dapat dituliskan sebagai penjumlahan tiga bilangan bulat berurutan. Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu bilangan $3^{k+1}$ dapat dituliskan sebagai penjumlahan tiga bilangan bulat berurutan.
Karena $P(k)$ benar, kita dapat tuliskan $3^k = (m-1) + m + (m+1) = 3m$ untuk suatu bilangan bulat $m.$ Perhatikan bahwa
$$\begin{aligned} 3^{k + 1} & = 3^k \cdot 3 \\ & = (3m) \cdot 3 && (\text{Hipotesis induksi}) \\ & = 3m + 3m + 3m \\ & = (3m-1) + 3m + (3m+1). \end{aligned}$$Karena $m$ bulat, $3m$ juga bulat.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$ 

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan papan berpetak dengan ukuran $6 \times 2^n$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L.
Langkah Basis:
$P(1)$ benar karena papan berpetak dengan ukuran $6 \times 2$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L seperti yang tampak pada gambar berikut.

Langkah Induktif:
Misalkan $P(k)$ benar untuk sembarang $k \in \mathbb{N}.$ Akan ditunjukkan bahwa $P(k+1)$ benar, artinya papan berpetak dengan ukuran $6 \times 2^{k+1}$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L untuk $k \in \mathbb{N}.$
Perhatikan bahwa papan berpetak dengan ukuran $6 \times 2^{k+1}$ dapat dipandang sebagai gabungan dua papan berukuran $6 \times 2^k.$ Berdasarkan hipotesis induksi, papan berukuran $6 \times 2^k$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ $\blacksquare$  

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan setiap papan berpetak dengan ukuran $2^n \times 2^n$ yang satu petak sembarangnya dihilangkan dapat selalu ditutupi oleh potongan tiga petak berbentuk huruf L.
Langkah Basis:
$P(1)$ benar seperti yang ditunjukkan pada gambar berikut. Petak putih merepresentasikan petak yang dihilangkan.
Langkah Induktif:
Misalkan $P(k)$ menyatakan setiap papan berpetak dengan ukuran $2^k \times 2^k$ yang satu petak sembarangnya dihilangkan dapat selalu ditutupi oleh potongan tiga petak berbentuk huruf L untuk sembarang $k \in \mathbb{N}.$ Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ benar, artinya papan berpetak dengan ukuran $2^{k+1} \times 2^{k+1}$ dapat diperlakukan serupa.
Perhatikan bahwa $2^{k+1} \times 2^{k+1}$ dapat ditulis sebagai $4 \times (2^k \times 2^k).$ Dengan kata lain, papan tersebut dapat dibagi menjadi $4$ papan yang lebih kecil dengan ukuran $2^k \times 2^k.$ Satu petak yang hilang pasti terletak pada salah satu papan kecil itu. Jadi, kita bisa meletakkan potongan tiga petak berbentuk huruf L sedemikian sehingga satu petak masing-masing termuat pada tiga papan kecil lain yang tidak dihilangkan petaknya. Perhatikan gambar ilustrasi berikut agar lebih jelas.
Akibatnya, $4$ papan berukuran $2^k \times 2^k$ memiliki satu petak yang dihilangkan. Berdasarkan hipotesis induksi, kita bisa menutupi setiap papan seperti itu dengan potongan tiga petak berbentuk huruf L.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ $\blacksquare$ 

Misalkan $n$ merupakan bilangan cacah. Misalkan juga $P(n)$ menyatakan ada setidaknya satu orang yang tidak terlempar kue ketika terdapat $m = 2n + 1$ orang.
Langkah Basis:
$P(0)$ benar karena hanya ada $m = 2(0) + 1 = 1$ orang sehingga tidak ada lemparan kue yang terjadi. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$  $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ benar, artinya ada setidaknya satu orang yang tidak terlempar kue ketika terdapat $m = 2(k+1) + 1 = 2k + 3$ orang untuk bilangan cacah $k.$
Misalkan $d(X, Y)$ menyatakan jarak dua orang, $X$ dan $Y.$ Dari $2k+3$ orang, cari dua orang yang memiliki jarak terdekat, katakanlah $A$ dan $B$ sehingga $d(A, B) < d(X, Y)$ untuk sembarang orang $X$ dan $Y$ dengan $(A, B) \neq (X, Y).$ $A$ dan $B$ tentu akan saling melempar kue. Pandang orang tersisa selain $A$ dan $B$, yaitu sebanyak $2k+1$ orang. Berdasarkan hipotesis induksi bahwa $P(k)$ benar, ada setidaknya satu orang dari $2k+1$ orang tersebut yang tidak terlempar kue.
Jadi, $P(k+1)$ terbukti benar. Karena $P(0)$ benar dan untuk sembarang bilangan cacah $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan cacah $n.$ $\blacksquare$ 

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n) : (1 + a)^n \ge 1 + an.$
Langkah Basis:
$P(1)$ benar karena jelas bahwa $(1 + a)^1 \ge 1 + a(1).$ Langkah basis selesai.
Langkah Induktif:
Misalkan $P(k)$ menyatakan $(1 + a)^k \ge 1 + ak$ untuk sembarang bilangan asli $k.$ Asumsikan $P(k)$ benar. Akan dibuktikan bahwa $P(k+1)$ benar yang menyatakan bahwa $(1 + a)^{k+1} \ge 1 + a(k+1)$ untuk setiap bilangan asli $k.$
Perhatikan bahwa
$$\begin{aligned} (1 + a)^{k+1} & = (1+a)^k \cdot (1+a) \\ & \ge (1+ak)(1+a) && (\text{Hipotesis induksi}) \\ & = 1 + a + ak + a^2k \\ & = 1 + a(k+1) + a^2k \\ & \ge 1 + a(k+1). && (a^2k \ge 0) \\ \end{aligned}$$Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n) : A^n = \begin{pmatrix} a^n & 0 \\ 0 & b^n \end{pmatrix}.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$$P(1): A^1 = \begin{pmatrix} a^1 & 0 \\ 0 & b^1 \end{pmatrix} = \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}.$$Pernyataan ini jelas benar. Untuk itu, $P(n)$ bernilai benar untuk $n = 1$. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$$P(k): A^k = \begin{pmatrix} a^k & 0 \\ 0 & b^k \end{pmatrix}.$$Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$$P(k+1): A^{k+1} = \begin{pmatrix} a^{k+1} & 0 \\ 0 & b^{k+1} \end{pmatrix}.$$Perhatikan bahwa menurut aturan perpangkatan dan perkalian matriks, kita peroleh
$$\begin{aligned} A^{k+1} & = A^k \cdot A \\ & = \begin{pmatrix} a^k & 0 \\ 0 & b^k \end{pmatrix} \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} \\ & = \begin{pmatrix} a^k \cdot a + 0 \cdot 0 & a^k \cdot 0 + 0 \cdot b \\ 0 \cdot a + b^k \cdot 0 & 0 \cdot 0 + b^k \cdot b \end{pmatrix} \\ & = \begin{pmatrix} a^{k+1} & 0 \\ 0 & b^{k+1} \end{pmatrix}. \end{aligned}$$Jadi, pernyataan $P(k+1)$ terbukti benar. Ini berarti kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, $P(n)$ benar untuk setiap $n \in \mathbb{N}$. $\blacksquare$

Perhatikan bahwa kita dapat mendefinisikan urutan pada $\mathbb{N_0} \times \mathbb{N_0}$ dengan mengatakan bahwa $(x_1, y_1) < (x_2, y_2)$ jika $x_1 < x_2$ atau ($x_1 = x_2$ dan $y_1 < y_2$) yang selanjutnya sebagai pengurutan leksikografik (lexicographic ordering).

Kita bisa membuktikan $S_{m,~n} = m + n$ dengan menggunakan induksi matematika yang dirampatkan (generalized mathematical induction). Langkah basisnya adalah menunjukkan bahwa rumus yang diberikan berlaku untuk $(m, n) = (0, 0).$ Langkah induktifnya adalah menunjukkan bahwa jika rumus itu berlaku untuk setiap pasangan yang lebih kecil dari $(m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0},$ maka rumus itu juga berlaku untuk $(m, n).$
Langkah Basis:
Misalkan $(m, n) = (0, 0).$ Nilai awal barisan yang didefinisikan secara rekursif tersebut adalah $S_{0, 0} = 0.$ Lebih lanjut, dari rumus yang diberikan, kita peroleh
$$S_{m, ~n} = m + n \rightarrow S_{0, 0} = 0 + 0 = 0.$$Langkah basis selesai.
Langkah Induktif:
Misalkan $S_{m^\prime,~n^\prime} = m^\prime + n^\prime$ berlaku kapan pun selama $(m^\prime, n^\prime) < (m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0}.$

Kasus 1: $n = 0$
Jika $n = 0,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = {\color{red}{S_{m-1,~n}}} + 1.~\color{blue}{\bigstar}$$ Karena $(m-1, n) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m-1, n)$, yaitu $S_{m-1,~n} = (m-1) + n.$ Dari $\color{blue}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = {\color{red}{(m-1)} + n} + 1 \\ & = m + n. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$

Kasus 2: $n \neq 0$
Jika $n \neq 0,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = \color{red}{S_{m,~n-1}} + 1.~\color{purple}{\bigstar}$$ Karena $(m, n-1) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m, n-1)$, yaitu $S_{m,~n-1} = m + (n-1).$ Dari $\color{purple}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = \color{red}{m + (n-1)} + 1 \\ & = m + n. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$
Langkah induktif selesai.

Berdasarkan prinsip induksi matematika, terbukti bahwa barisan tersebut dapat dinyatakan secara eksplisit sebagai $S_{m, ~n} = m + n.$ $\blacksquare$

Perhatikan bahwa kita dapat mendefinisikan urutan pada $\mathbb{N} \times \mathbb{N}$ dengan mengatakan bahwa $(x_1, y_1) < (x_2, y_2)$ jika $x_1 < x_2$ atau ($x_1 = x_2$ dan $y_1 < y_2$) yang selanjutnya sebagai pengurutan leksikografik (lexicographic ordering).

Kita bisa membuktikan $S_{m,~n} = 2(m+n)+1$ dengan menggunakan induksi matematika yang dirampatkan (generalized mathematical induction). Langkah basisnya adalah menunjukkan bahwa rumus yang diberikan berlaku untuk $(m, n) = (1, 1).$ Langkah induktifnya adalah menunjukkan bahwa jika rumus itu berlaku untuk setiap pasangan yang lebih kecil dari $(m, n)$ menurut pengurutan leksikografik dari $\mathbb{N} \times \mathbb{N},$ maka rumus itu juga berlaku untuk $(m, n).$
Langkah Basis:
Misalkan $(m, n) = (1, 1).$ Nilai awal barisan yang didefinisikan secara rekursif tersebut adalah $S_{1, 1} = 5.$ Lebih lanjut, dari rumus yang diberikan, kita peroleh
$$S_{m,~ n} = 2(m+n)+1 \rightarrow S_{1, 1} = 2(1+1)+1=5.$$Langkah basis selesai.
Langkah Induktif:
Misalkan $S_{m^\prime,~n^\prime} = 2(m^\prime + n^\prime) + 1$ berlaku kapan pun selama $(m^\prime, n^\prime) < (m, n)$ menurut pengurutan leksikografik dari $\mathbb{N} \times \mathbb{N}.$

Kasus 1: $n = 1$
Jika $n = 1,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = {\color{red}{S_{m-1,~n}}} + 2.~\color{blue}{\bigstar}$$ Karena $(m-1, n) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m-1, n)$, yaitu $S_{m-1,~n} = 2((m-1)+n)+1.$ Dari $\color{blue}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = \color{red}{(2((m-1)+n)+1)} + 2  \\ & = 2(m+n) + 1. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$

Kasus 2: $n \neq 1$
Jika $n \neq 1,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = \color{red}{S_{m,~n-1}} + 2.~\color{purple}{\bigstar}$$ Karena $(m, n-1) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m, n-1)$, yaitu $S_{m,~n-1} = 2(m+(n-1))+1.$ Dari $\color{purple}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = \color{red}{(2(m+(n-1))+1)} + 2 \\ & = 2(m+n)+1. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$
Langkah induktif selesai.

Berdasarkan prinsip induksi matematika, terbukti bahwa barisan tersebut dapat dinyatakan secara eksplisit sebagai $S_{m, ~n} = 2(m+n)+1.$ $\blacksquare$

Perhatikan bahwa kita dapat mendefinisikan urutan pada $\mathbb{N_0} \times \mathbb{N_0}$ dengan mengatakan bahwa $(x_1, y_1) < (x_2, y_2)$ jika $x_1 < x_2$ atau ($x_1 = x_2$ dan $y_1 < y_2$) yang selanjutnya sebagai pengurutan leksikografik (lexicographic ordering).

Kita bisa membuktikan $a_{m, n} = m + \dfrac{n(n+1)}{2}$ dengan menggunakan induksi matematika yang dirampatkan (generalized mathematical induction). Langkah basisnya adalah menunjukkan bahwa rumus yang diberikan berlaku untuk $(m, n) = (0, 0).$ Langkah induktifnya adalah menunjukkan bahwa jika rumus itu berlaku untuk setiap pasangan yang lebih kecil dari $(m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0},$ maka rumus itu juga berlaku untuk $(m, n).$
Langkah Basis:
Misalkan $(m, n) = (0, 0).$ Nilai awal barisan yang didefinisikan secara rekursif tersebut adalah $a_{0, 0} = 0.$ Lebih lanjut, dari rumus yang diberikan, kita peroleh
$$a_{m, ~n} = m + \dfrac{n(n+1)}{2} \rightarrow a_{0, 0} = 0 + \dfrac{0(0+1)}{2} = 0.$$Langkah basis selesai.
Langkah Induktif:
Misalkan $a_{m^\prime,~n^\prime} = m^\prime + \dfrac{n^\prime(n^\prime+1)}{2}$ berlaku kapan pun selama $(m^\prime, n^\prime) < (m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0}.$

Kasus 1: $n = 0$
Jika $n = 0,$ barisan didefinisikan secara rekursif sebagai $$a_{m,~n} = \color{red}{a_{m-1,~n}} + 1.~\color{blue}{\bigstar}$$ Karena $(m-1, n) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m-1, n)$, yaitu $a_{m-1,~n} = (m-1) + \dfrac{n(n+1)}{2}.$ Dari $\color{blue}{\bigstar}$, kita peroleh
$$\begin{aligned} a_{m, ~n} & = \color{red}{(m-1) + \dfrac{n(n+1)}{2}} + 1 \\ & = m + \dfrac{n(n+1)}{2}. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$

Kasus 2: $n > 0$
Jika $n > 0,$ barisan didefinisikan secara rekursif sebagai $$a_{m,~n} = \color{red}{a_{m,~n-1}} + n.~\color{purple}{\bigstar}$$ Karena $(m, n-1) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m, n-1)$, yaitu $a_{m,~n-1} = m + \dfrac{(n-1)(n)}{2}.$ Dari $\color{purple}{\bigstar}$, kita peroleh
$$\begin{aligned} a_{m, ~n} & = \color{red}{m + \dfrac{(n-1)(n)}{2}} + n \\ & = m + \dfrac{(n-1)(n) + 2n}{2} \\ & = m + \dfrac{(n(n+1)}{2}. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$
Langkah induktif selesai.

Berdasarkan prinsip induksi matematika, terbukti bahwa barisan tersebut dapat dinyatakan secara eksplisit sebagai $a_{m,~n} = m + \dfrac{n(n+1)}{2}.$ $\blacksquare$

Misalkan $n \ge 2$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan bahwa jika $A_1, A_2, \cdots, A_n$ masing-masing adalah himpunan, maka berlaku $$\overline{A_1 \cap A_2 \cap \cdots \cap A_n} = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_n}.$$Langkah Basis:
$P(2)$ benar karena untuk $n = 2,$
$$\overline{A_1 \cap A_2} = \overline{A_1} \cup \overline{A_2}$$sesuai dengan hukum De Morgan untuk dua himpunan.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k \ge 2,$ $P(k)$ benar, yaitu proposisi bahwa jika $A_1, A_2, \cdots, A_k$ masing-masing adalah himpunan, maka berlaku $$\overline{A_1 \cap A_2 \cap \cdots \cap A_k} = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k}.$$Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu proposisi bahwa jika $A_1, A_2, \cdots, A_k, A_{k+1}$ masing-masing adalah himpunan, maka berlaku $$\overline{A_1 \cap A_2 \cap \cdots \cap A_k \cap A_{k+1}} = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k} \cup \overline{A_{k+1}}.$$Perhatikan bahwa
$$\begin{aligned} \overline{A_1 \cap A_2 \cap \cdots \cap A_k \cap A_{k+1}} & = \overline{(A_1 \cap A_2 \cap \cdots \cap A_k) \cap A_{k+1}} && (\text{Hukum Asosiatif}) \\ & = \overline{A_1 \cap A_2 \cap \cdots \cap A_k} \cup \overline{A_{k+1}} && (\text{Hukum De Morgan 2 Himpunan}) \\ & = (\overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k}) \cup \overline{A_{k+1}} && (\text{Hipotesis Induksi}) \\ & = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k} \cup \overline{A_{k+1}}. && (\text{Hukum Asosiatif}) \end{aligned}$$Jadi, terbukti bahwa $P(k+1)$ benar.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan asli $n \ge 2.$

Misalkan $n \ge 2$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan bahwa jika $A, B_1, B_2, \cdots, B_n$ masing-masing adalah himpunan, maka
$$A \cap (B_1 \cup B_2 \cup \cdots \cup B_n) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_n).$$Langkah Basis:
$P(2)$ benar karena untuk $n = 2,$
$$A \cap (B_1 \cup B_2) = (A \cap B_1) \cup (A \cap B_2)$$sesuai dengan hukum distributif untuk dua himpunan.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k \ge 2,$ $P(k)$ benar, yaitu proposisi bahwa jika $A, B_1, B_2, \cdots, B_k$ masing-masing adalah himpunan, maka
$$A \cap (B_1 \cup B_2 \cup \cdots \cup B_k) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_k).$$Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu proposisi bahwa jika $A, B_1, B_2, \cdots, B_k, B_{k+1}$ masing-masing adalah himpunan, maka
$$A \cap (B_1 \cup B_2 \cup \cdots \cup B_k \cup B_{k+1}) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_k) \cup (A \cap B_{k+1}).$$Perhatikan bahwa
$$\begin{aligned} A \cap (B_1 \cup B_2 \cup \cdots \cup B_k \cup B_{k+1}) & = A \cap ((B_1 \cup B_2 \cup \cdots \cup B_k) \cup B_{k+1}) && (\text{Hukum Asosiatif}) \\ & = (A \cap (B_1 \cup B_2 \cup \cdots \cup B_k)) \cup (A \cap B_{k+1}) && (\text{Hukum Distributif 2 Himpunan}) \\ & = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_k) \cup (A \cap B_{k+1}). && (\text{Hipotesis Induksi}) \end{aligned}$$Jadi, $P(k+1)$ terbukti benar. Karena $P(2)$ benar dan untuk sembarang bilangan asli $k \ge 2,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n \ge 2.$ $\blacksquare$ 

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan banyak untaian bit dengan panjang $n$ bit yang memuat bit $1$ sebanyak genap adalah $2^{n-1}.$
Langkah Basis:
$P(1)$ benar karena untaian bit dengan panjang $1$ bit yang memuat bit $1$ sebanyak genap hanya $0$ (bit $1$-nya tidak ada, alias 0, dan $0$ adalah bilangan genap). Hal ini sesuai dengan rumus $2^{n-1} = 2^{1-1} = 1.$
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k)$ benar, yaitu banyak untaian bit dengan panjang $k$ bit yang memuat bit $1$ sebanyak genap adalah $2^{k-1}.$ Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu banyak untaian bit dengan panjang $k+1$ bit yang memuat bit $1$ sebanyak genap adalah $2^{k}.$
Perhatikan bahwa untuk untaian bit dengan panjang $k$ bit, terdapat $2^k$ untaian bit berbeda yang dapat dibuat. Jika bit ke-$(k+1)$ diikutkan, akan ada $2^{k+1} = \color{red}{2} \cdot 2^k$ untaian bit berbeda yang dapat dibuat. Menurut hipotesis induksi, banyak untaian bit dengan panjang $k$ bit yang mempunyai bit $1$ sebanyak genap adalah $2^{k-1}.$ Ini berarti banyak untaian bit dengan panjang $k+1$ bit yang mempunyai bit $1$ sebanyak genap adalah $\color{red}{2}$ kali lipatnya, yaitu $2 \cdot 2^{k-1} = 2^k.$ Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ $\blacksquare$

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan bahwa jika ada $n$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{n(n-1)}{2}.$
Langkah Basis:
$P(1)$ benar karena untuk $n=1$ orang tamu, tidak ada jabat tangan yang terjadi, atau $\dfrac{1(1-1)}{2} = 0$ kali.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k)$ benar, yaitu jika ada $k$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{k(k-1)}{2}.$ Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu jika ada $k+1$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{(k+1)k}{2}.$
Perhatikan bahwa untuk $k+1$ orang tamu, banyak jabat yang terjadi sama dengan banyak jabat tangan pada $k$ orang tamu ditambah dengan banyak jabat tangan yang dilakukan oleh tamu ke-$(k+1).$ Menurut hipotesis induksi, $k$ orang tamu ini akan melakukan jabat tangan sebanyak $\dfrac{k(k-1)}{2}.$ Tamu ke-$(k+1)$ ini akan berjabat tangan sebanyak $k$ kali dengan masing-masing $k$ orang tamu lainnya (masing-masing sekali) sehingga banyak jabat tangan keseluruhan adalah
$$\begin{aligned} \dfrac{k(k-1)}{2} + k & = \dfrac{k(k-1}{2} + \dfrac{2k}{2} \\ & = \dfrac{k^2+k}{2} \\ & = \dfrac{(k+1)k}{2}. \end{aligned}$$Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ $\blacksquare$

Kesalahan pembuktian dengan menggunakan induksi kuat di atas terjadi pada langkah induktif. Perhatikan bahwa ekspresi $a^{n-1}$ dimunculkan, padahal untuk $n = 0,$ kita dapatkan $a^{-1}$ yang nilainya tidak diasumsikan pada hipotesis induksi. Akibatnya, pembuktian menjadi cacat dan kita peroleh kesimpulan yang kurang tepat.